A storage system is a computer that provides storage service relating to the organization of information on writable persistent storage devices, such as memories, tapes or disks. The storage system is commonly deployed within a storage area network (SAN) or a network attached storage (NAS) environment. When used within a NAS environment, the storage system may be embodied as a file server including an operating system that implements a file system to logically organize the information as a hierarchical structure of data containers, such as directories and files on, e.g., the disks. When used within a SAN environment, the storage system may organize the information in the form of databases or files. Where the information is organized as files, the client requesting the information typically maintains file mappings and manages file semantics, while its requests (and system responses) address the information in terms of block addressing on disk using, e.g., logical unit numbers.
Each “on-disk” file may be implemented as set of data structures, i.e., disk blocks, configured to store information, such as the actual data for the file. These data blocks are typically organized within a volume block number (vbn) space that is maintained by the file system. The file system may also assign each data block in the file a corresponding “file offset” or file block number (fbn) position in the file. The file system typically assigns sequences of fbns on a per-file basis, whereas vbns are assigned over a larger volume address space. That is, the file system organizes the data blocks within the vbn space as a volume; each volume may be, although is not necessarily, associated with its own file system. The file system typically consists of a contiguous range of vbns from zero to n, for a file system of size n−1 blocks.
The storage system may be further configured to operate according to a client/server model of information delivery to thereby allow many clients to access files stored on the system. In this model, the client may comprise an application, such as a database application, executing on a computer that “connects” to the storage system over a computer network, such as a point-to-point link, shared local area network, wide area network or virtual private network implemented over a public network, such as the Internet. The client typically communicates with the storage system by exchanging discrete frames or packets of data according to pre-defined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In addition, the client may request the services of the system by issuing file system protocol messages over the network to the storage system.
A file system may have the capability to generate a snapshot of its active file system. An “active file system” is a file system to which data can be both written and read, or, more generally, an active store that responds to both read and write operations. The snapshot, i.e., snapshot data, refers to a copy of file system data that diverges from the active file system over time as the active file system is modified. Snapshots are well-known and described in U.S. patent application Ser. No. 09/932,578 entitled Instant Snapshot by Blake Lewis et al., TR3002 File System Design for a NFS File Server Appliance by David Hitz et al., published by Network Appliance, Inc. and in U.S. Pat. No. 5,819,292 entitled Method for Maintaining Consistent States of a File System and For Creating User-Accessible Read-Only Copies of a File System, by David Hitz et al., each of which is hereby incorporated by reference as though fully set forth herein.
A common type of file system is a “write in-place” file system, where the locations of the data structures on disk are typically fixed. That is, the disk is “viewed” as a large sequential array of blocks and changes (updates) to the data of a file stored in the blocks are made in-place, i.e., data is overwritten at the same disk locations. The write in-place file system may assume a layout such that the data is substantially contiguously arranged on disks. This disk layout results in efficient access operations, particularly for sequential read operations, directed to the disks. Updating of data in-place thus maintains efficient read access to the data, but often at the expense of write performance.
Another type of file system is a journal or log-structured file system that generally does not overwrite data on disks. If a data block on disk is retrieved (read) from disk into memory of the storage system and changed or “dirtied” with new data provided by, e.g., an application, the data block is stored (written) to a new location on disk to optimize write performance. The file system typically uses block allocation data structures, such as an active map and one or more snapshot maps, to select free blocks within its vbn space to which to write the dirty blocks. As used herein, an active map denotes a file including a bitmap associated with a free status of the active file system. The snapshot map denotes a file including a bitmap associated with the vacancy of blocks of a snapshot. By examining the active and snapshot maps, the file system can determine whether a block is in use by either the active file system or any snapshot.
The block allocation data structures describe block usage within the file system and, as such, represent snapshot and file system metadata. As used herein, the term metadata denotes information used to describe, e.g., data containers, such as snapshots and files. In particular, the snapshot map data structures are used and maintained by the file system as existing infrastructure for the volume. However, the maintenance of such metadata within the block allocation structures may be expensive in terms of storage and access efficiencies.